﻿using System;
using System.Text;

//于2024年3月14日13:03:00

namespace BigIntegerOperation
{
  

    class Program
    {


        //大数加法
        static string Add(string num1, string num2)
        {
            
            int carry = 0;
            string result = "";

            // 从最低位开始逐位相加
            int i = Pretreatment.PreOne(num1);
            int j = Pretreatment.PreOne(num2);


            while (i >= 0 || j >= 0 || carry > 0)
            {
                int digit1 = (i >= 0) ? num1[i] - '0' : 0;//将字符串中的第i位元素转变为number便于求和
                int digit2 = (j >= 0) ? num2[j] - '0' : 0;
                int sum = digit1 + digit2 + carry;
                carry = sum / 10; // 进位
                result = (sum % 10).ToString() + result; // 字符串拼接，把当前位的结果添加到最终结果的前面
                i--;
                j--;    
            }

            return result;
        }
        //大数减法
        static string Subtract(string num1, string num2)
        {
            string result = "";
            int borrow = 0;

            // 从最低位开始逐位相减
            int i = Pretreatment.PreOne(num1);
            int j = Pretreatment.PreOne(num2);

            while (i >= 0)
            {
                int digit1 = num1[i] - '0';
                int digit2 = (j >= 0) ? num2[j] - '0' : 0;

                // 减去借位
                int diff = digit1 - digit2 - borrow;

                if (diff < 0)
                {
                    diff += 10; // 借10
                    borrow = 1;
                }
                else
                {
                    borrow = 0;
                }

                result = (diff).ToString() + result; // 把当前位的结果添加到最终结果的前面
                i--;
                j--;
            }

            // 去除结果中的前的零
            while (result.Length > 0 && result[0] == '0')
            {

                    result = result.Substring(1);

            }

            return (result.Length == 0) ? "0" : result;
        }

        static string Multiply(string num1, string num2)
        {
            int n = num1.Length;
            int m = num2.Length;

            /*基本情况：如果有一个操作数为0，则结果为0
             * 1.输入的字符串为0
              *2.输入字符串为空，长度为0
            */
            if (m == 0 || n == 0 || num1 == "0" || num2 == "0")
            {
                return "0";
            }

            // 如果有一个操作数为1，返回另一个数为结果
            if (num1 == "1")
            {
                return num2;
            }

            if (num2 == "1")
            {
                return num1;
            }

            // 如果操作数很小，直接相乘
            if (n <= 2 || m <= 2)
            {   //将字符串解析为长整型
                long longResult = long.Parse(num1) * long.Parse(num2);
                return longResult.ToString();
            }

            // 将操作数切分成两部分，并存储n和m两个整数中较小值的一半
            int mid = Math.Min(n, m) / 2;
            string num1Low = num1.Substring(0, n - mid);
            string num1High = num1.Substring(n - mid);
            string num2Low = num2.Substring(0, m - mid);
            string num2High = num2.Substring(m - mid);

            // karatsuba算法思想，推导见文档

            string r0 = Multiply(num1Low, num2Low);
            string r1 = Multiply(num1High, num2High);
            string r2 = Multiply(Add(num1Low, num1High), Add(num2Low, num2High));
            string r3 = Subtract(Subtract(r2, r1), r0);

            // 计算最终的乘积
            string result = Add(Add(r0 + new string('0', mid * 2), r1), r3 + new string('0', mid));

            return result;
        }




    //比较函数
        static bool Compare(string num1, string num2)
        {
            int len1 = num1.Length;
            int len2 = num2.Length;
            if (len1 < len2)
                return false;
            else if (len1 == len2 && num1.CompareTo(num2) < 0) //比较两个字符串的字典顺序 eg:例如，数字序列“123”在“124”之前，因为尽管前两位相同，但在第三位上“3”小于“4”
                return false;
            return true;
        }

        //大数除法
         static DivisionResult Div(string a, string b)
        {
            string remainder = "";
            StringBuilder quotient = new StringBuilder();//实例化StringBuilder对象,处理字符

            if (b == "0")
            {
                Console.WriteLine("NULL");
                return new DivisionResult("", "error!!");
            }

            // 去掉字符串前缀0
            a = a.TrimStart('0');
            b = b.TrimStart('0');

            // 如果被除数小于除数，商为0，余数为被除数
            if (!Compare(a, b))
            {
                Console.WriteLine("0 " + a);//返回余数中止计算
                return new DivisionResult("", a);
            }

            int len = a.Length;
            for (int i = 0; i < len; i++)
            {
                int count = 0;
                remainder += a[i];

                while (Compare(remainder, b))
                {
                    remainder = Subtract(remainder, b);
                    count++;
                }

                // 添加商的数字
                if (count != 0)
                    quotient.Append(count);
            }
 
            return new DivisionResult(quotient.ToString(), remainder);

        
        }



        static void Main(string[] args)
        {
            // 相乘的两个整数
            
            string num1 = "676543210987654321098765432109876543210";
            string num2 = "301000000000000000000000000000000000000";
            DivisionResult divisionResult = Div(num1, num2);
            string result1 = Add(num1, num2);
            string result2 = Subtract(num1, num2);
            string result3 = Multiply(num1, num2);
            string result4 = divisionResult.Quotient;
            string result5 = divisionResult.Remainder;
            Console.WriteLine(new string('=', 50) + "大数四则运算" + new string('=', 50));
            Console.WriteLine("num1 = "+ NumFormat.Format(num1));
            Console.WriteLine("num2 = "+ NumFormat.Format(num2));
            Console.WriteLine("num1 + num2 = " + NumFormat.Format(result1));
            Console.WriteLine("num1 - num2 = " + NumFormat.Format(result2));
            Console.WriteLine("num1 * num2 = " + NumFormat.Format(result3));
            Console.WriteLine("num1 / num2 = " + NumFormat.Format(result4));
            Console.WriteLine("num1 % num2 =  " + NumFormat.Format(result5));
            Console.WriteLine("两个整数积位数为 = " + result3.Length);
            Console.ReadLine();
        }
    }
}